package com.leetcode.专项突破.二叉树;

import com.leetcode.common.model.TreeNode;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @author 覃国强
 * @date 2022-04-10 16:21
 */
public class LevelOrder {

  static
  class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
      List<List<Integer>> answers = new ArrayList<>();
      if (root == null) {
        return answers;
      }
      Deque<TreeNode> queue = new ArrayDeque<>();
      TreeNode last = root;
      TreeNode curLast = root;
      queue.add(root);
      List<Integer> level = new ArrayList<>();
      while (!queue.isEmpty()) {
        TreeNode remove = queue.remove();
        level.add(remove.val);
        if (remove.left != null) {
          queue.add(remove.left);
          curLast = remove.left;
        }
        if (remove.right != null) {
          queue.add(remove.right);
          curLast = remove.right;
        }
        if (last == remove) {
          answers.add(level);
          level = new ArrayList<>();
          last = curLast;
        }
      }
      return answers;
    }
  }

}
